#include<iostream>
#include"Quick.h"
using namespace std;

void Quick::sort(int* arr, int len) {
	int lo = 0;
	int hi = len - 1;
	sort(arr, lo, hi);
}

void Quick::sort(int* arr, int lo, int hi) {
	if (lo >= hi) {
		return;
	}

	int partition = this->partition(arr, lo, hi);
	sort(arr, lo, partition - 1);
	sort(arr, partition + 1, hi);
}

int Quick::partition(int* arr, int lo, int hi) {
	int key = arr[lo];
	int left = lo;
	int right = hi + 1;
	while (true)
	{
		while (less(key, arr[--right])) {
			if (right == lo) {
				break;
			}
		}
		while (less(arr[++left], key)) {
			if (left == hi) {
				break;
			}
		}

		if (left >= right) {
			break;
		}
		else
		{
			exch(arr, left, right);
		}
	}
	exch(arr, lo, right);
	return right;
}

bool Quick::less(int v, int w) {
	if (v < w) {
		return true;
	}
	return false;
}

void Quick::exch(int* arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}


void main08() {
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int len = sizeof(arr) / sizeof(arr[0]);
	Quick q;
	q.sort(arr, len);
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << endl;
	}
}
